Cycle and Circle Tests of Balance in Gain Graphs: Forbidden Minors and Their Groups

摘要

We examine two criteria for balance of a gain graph, one based on binarycycles and one on circles. The graphs for which each criterion is valid dependon the set of allowed gain groups. The binary cycle test is invalid, except forforests, if any possible gain group has an element of odd order. Assuming allgroups are allowed, or all abelian groups, or merely the cyclic group of order3, we characterize, both constructively and by forbidden minors, the graphs forwhich the circle test is valid. It turns out that these three classes of groupshave the same set of forbidden minors. The exact reason for the importance ofthe ternary cyclic group is not clear.